public class Solution309 {
    public int maxProfit(int[] prices) {
        if (prices.length==1){
            return 0;
        }
        int[] f=new int[prices.length];
        int[] g=new int[prices.length];
        f[0]=-prices[0];
        f[1]=Math.max(f[0],-prices[1]);
        g[1]=Math.max(0,prices[1]-prices[0]);
        for (int i=2;i<prices.length;i++){
            f[i]=Math.max(f[i-1],g[i-2]-prices[i]);
            g[i]=Math.max(g[i-1],f[i-1]+prices[i]);
        }
        return g[prices.length-1];
    }

    public static void main(String[] args) {
        System.out.println(new Solution309().maxProfit(new int[]{1,2,3,0,2}));
    }
}
